FIFO memories comprise addressable memory cells such as RAM (i.e., Random Access Memory) and memory access (e.g. read and write) control circuitry. Information (e.g., data, addresses, instructions) may be written to and read from the memory cells using the control circuitry. FIFO control circuitry relies on basic FIFO status information such as a read address pointer and a write address pointer to accurately keep track of which memory cells are due to be read and written, respectively, in accordance with first-in first-out functionality. Read and write functions are mutually dependent on read and write pointers. For instance, if a memory cell has been written but not yet read (as would be the case if the FIFO were full of unaccessed information) then it is not yet due to be written. Likewise, if a memory cell has previously been written and read but not subsequently written (as would be the case if the FIFO were “empty”) then it is not yet due to be read. If read and write functions were not made to be mutually dependent on FIFO status information such as read and write pointers then an undesirable underrun (i.e., overread) or overrun (i.e., overwrite) condition may occur.
In a synchronous FIFO memory the same clock is used to write to and read from the memory cells in the FIFO. In an asynchronous (e.g., multi-synchronous) FIFO memory, writes to and reads from the FIFO are not synchronized in a single clock domain. Multi-synchronous FIFO memories are utilized to allow independently clocked systems to communicate with one another by acting as a buffer between the systems. Even though reads and writes may occur independently in time in multi-synchronous FIFO memories, they remain mutually dependent on FIFO status information such as read address and write address pointers. Because of this mutual dependence on the same status information, the status information must be made available in each independent asynchronous time domain. Passing multiple FIFO status signals between asynchronous time domains naturally results in added complexity for functions performed by asynchronous FIFO memories, relative to more simplistic synchronous FIFOs.
Because FIFO memories generally comprise an array of addressable memory cells arranged as rows and columns, read address and write address pointers generally require several bits to address individual memory cells or groups (e.g., rows) of memory cells such as a row of 16 memory cells storing a 16-bit word of information. Each address bit is a signal unto itself. For example, if a FIFO has eight rows for storing eight 16-bit words, the read pointer would require three address bits and the write pointer would require and additional three address bits for a total of six signals that must be passed between asynchronous time domains. Larger FIFO memories increase the number of signals, which only increases timing complexity.
Techniques to simplify timing requirements for signals passed between asynchronous domains include Gray coding. For example, if an address pointer increments, e.g., after a read or write, from row 7 (i.e., binary 111) to row 0 (i.e., binary 000), all three signals for the address pointer change. Popping and pushing involve increments by one of the address pointer. By encoding the binary address using Gray coding, only one bit changes per increment of an address pointer, and that at most one bit can be changing at the instant that the pointer is parted across the clock domain. The value that is ported is either the Gray-coded value before the lo increment or the Gray-coded value after the increment. Retry changes the pointer value by an arbitrary amount. In that case, the Gray-code encoding would change is several bit positions. The Gray-code encoded value would not be portable across clock domains, were the change in pointer value to occur in one clock cycle. By spreading out the change in pointer value that retry causes across multiple cycles, such that the pointer value changes by at most 1 from cycle to cycle, the Gray-coded pointer value becomes portable at all times.
U.S. Pat. No. 5,278,956 describes a synchronous FIFO (one clock domain) with variable depth and variable threshold for defining the fall/empty conditions in the FIFO.
U.S. Pat. Nos. 4,873,666 and 5,079,693 describes retry (re-read and rewrite) mechanisms on both read and write sides of a synchronous FIFO, using temporary registers to hold copies of respective read and write counters. There is one clock domain, U.S. Pat. No. 6,434,676 describes a generalization of a re-read mechanism, allowing multiple re-reads at random locations. Again, there is one clock domain and the FIFO is synchronous.
Due to timing complexities, multi-synchronous FIFO memories are generally fixed in size and lack functionality. Given that size requirements for multi-synchronous FIFO memories vary from one design to the next and given that not every read or write transaction is successful, it would be advantageous to overcome the timing complexities to develop a multi-synchronous FIFO having programmable size and transaction retry capability, and a single Gray-code encode/decode and synchronization circuit that is fixed and works for all FIFO sizes.